package com.排序.排序基础;

public class 堆排序 {
    public static void sort(int[] a){
        heapify(a, a.length);
        for (int right = a.length - 1; right > 0; right--) {
            swap(a, 0, right);
            down(a, 0, right);
        }
    }

    private static void heapify(int[] array, int size) {
        for(int i = size/2 - 1; i >= 0; i--){
            down(array, i, size);
        }
    }

    private static void down(int[] array, int parent, int size)  {
        while (true){
            int left = 2 * parent + 1;
            int right = left + 1;
            int max = parent;
            if(left < size && array[left] > array[max]){
                max = left;
            }
            if(right < size && array[right] > array[max]){
                max = right;
            }
            if(max == parent){
                break;
            }
            swap(array, max, parent);
            parent = max;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
